googologywikiaorg-20200223-history
Ordinal notation
An ordinal collapsing function (OCF) is a method of naming large ordinals using even larger ones. More specifically, ordinal collapsing functions take the structures found in large (often uncountable) ordinals and mirror those structures onto smaller ordinals. OCFs are employed as notations for large recursive ordinals, for which they have the most relevance to googology. There are many OCFs in use, often similar to each other and easily confused (some even use the same symbols), but most are nearly or exactly equal. Popular systems include Pohler's \(\psi\), Feferman's \(\theta\), Weiermann's \(\vartheta\), Buchholz's extension of Pohler's \(\psi\), and an uncountable extension of the Veblen function \(\phi\). Bachmann's \(\psi\) Heinz Bachmann's \(\psi\) function was the first true ordinal collapsing function. It is somewhat cumbersome as it depends on fundamental sequences for all limit ordinals. Feferman's \(\theta\) Feferman's \(\theta\)-functions constitute a hierarchy of single-argument functions \(\theta_\alpha: \text{On} \mapsto \text{On}\) for \(\alpha \in \text{On}\). It is often considered a two-argument function with \(\theta_\alpha(\beta)\) written as \(\theta\alpha\beta\). It is defined like so: \begin{eqnarray*} C_0(\alpha, \beta) &=& \beta \cup \{0, \omega_1, \omega_2, \ldots, \omega_\omega\}\\ C_{n+1}(\alpha, \beta) &=& \{\gamma + \delta, \theta_\xi(\eta) | \gamma, \delta, \xi, \eta \in C_n(\alpha, \beta); \xi < \alpha\} \\ C(\alpha, \beta) &=& \bigcup_{n < \omega} C_n (\alpha, \beta) \\ \theta_\alpha(\beta) &=& \min\{\gamma | \gamma \not\in C(\alpha, \gamma) \wedge \forall \delta < \beta: \theta_\alpha(\delta) < \gamma\} \\ \end{eqnarray*} Informally: * An ordinal \(\beta\) is considered \(\alpha\)-critical iff it cannot be constructed with the following elements: ** all ordinals less than \(\beta\), ** all ordinals in the set \(\{0, \omega_1, \omega_2, \ldots, \omega_\omega\}\), ** the operation \(+\), ** \(\theta\xi\eta\) for \(\xi < \alpha\) and any ordinal \(\eta\). * \(\theta_\alpha\) is the enumerating function for all \(\alpha\)-critical ordinals. Buchholz discusses a set he calls \(\theta(\omega + 1)\), which is the set of all ordinals describable with \(\{0, \omega_1, \omega_2, \ldots, \omega_\omega\}\) and finite applications of \(+\) and \(\theta\). Buchholz's \(\psi\) Buchholz's \(\psi\) is a hierarchy of single-argument functions \(\psi_v: \text{On} \mapsto \text{On}\) for \(v \leq \omega\), with \(\psi_v(\alpha)\) abbreviated as \(\psi_v\alpha\). Define \(\Omega_0 = 1\) and \(\Omega_v = \aleph_v\) for \(v > 0\), and let \(P(\alpha)\) be the set of distinct terms in the Cantor normal form of \(\alpha\) (with each term of the form \(\omega^\xi\) for \(\xi \in \text{On}\)): \begin{eqnarray*} C_v^0(\alpha) &=& \Omega_v\\ C_v^{n+1}(\alpha) &=& C_v^n(\alpha) \cup \{\gamma | P(\gamma) \subseteq C_v^n(\alpha)\} \cup \{\psi_v\xi | \xi \in \alpha \cap C_v^n(\alpha) \wedge \xi \in C_u(\xi) \wedge u \leq \omega\} \\ C_v(\alpha) &=& \bigcup_{n < \omega} C_v^n (\alpha) \\ \psi_v\alpha &=& \min\{\gamma | \gamma \not\in C_v(\alpha)\} \\ \end{eqnarray*} The limit of this system is \(\psi_0 \varepsilon_{\Omega_\omega + 1}\), the Takeuti-Feferman-Buchholz ordinal. Gro-Tsen's \(\psi\) A Wikipedia user under the name "Gro-Tsen" defined the following simpler variant of one of Buchholz's functions as a demonstration of how ordinal collapsing functions work. The popularity of the article led to widespread use of the modified function. \begin{eqnarray*} C_0(\alpha) &=& \{0, 1, \omega, \Omega\}\\ C_{n+1}(\alpha) &=& \{\gamma + \delta, \gamma\delta, \gamma^{\delta}, \psi(\eta) | \gamma, \delta, \eta \in C_n (\alpha, \beta); \eta < \alpha\} \\ C(\alpha) &=& \bigcup_{n < \omega} C_n (\alpha) \\ \psi(\alpha) &=& \min\{\beta \in \Omega|\beta \notin C(\alpha)\} \\ \end{eqnarray*} Informally: * \(C(\alpha)\) is the set of all ordinals constructible using only \(0\), \(1\), \(\omega\), \(\Omega\), and finite applications of the following functions: addition, multiplication, exponentiation, and \(\kappa \mapsto \psi(\kappa)\) (the latter only if \(\psi(\kappa)\) has yet been defined). * \(\psi(\alpha)\) is the smallest countable ordinal not in \(C(\alpha)\). Chris Bird uses this function throughout his googological papers.Chris Bird, pers. comm Bird's \(\theta\) Chris Bird devised the following shorthand for the extended Veblen function \(\varphi\): \- 1}a_{n - 1} + \cdots + \Omega^2a_2 + \Omega a_1 + a_0, b) = \varphi(a_{n - 1}, \ldots, a_2, a_1, a_0, b)\ \(\theta(\alpha, 0)\) is abbreviated as \(\theta(\alpha)\). This function is only defined for arguments less than \(\Omega^\omega\), and its outputs are limited by the small Veblen ordinal. In his papers, Bird erroneously uses \(\theta(\Omega^\omega)\) and higher values without properly defining the function. Wilken's \(\vartheta\) Wilken's \(\vartheta\) is more generic than other OCFs. Let \(\Omega_0\) be either \(1\) or a number of the form \(\varepsilon_\alpha\), let \(\Omega_1 > \Omega_0\) be an uncountable regular cardinal and for \(0 < i < \omega\) let \(\Omega_{i+1}\) be the successor cardinal to \(\Omega_i\). Then, for \(0 < n < \omega\) and \(0 \leq m < n\), define the following for \(\beta < \Omega_{m+1}\): \begin{eqnarray*} \Omega_m \cup \beta &\subseteq& C_m^n(\alpha, \beta) \\ \xi, \eta \in C_m^n(\alpha, \beta) &\Rightarrow& \xi + \eta \in C_m^n(\alpha, \beta) \\ \eta \in C_m^n(\alpha, \beta) \cap \Omega_{k + 2} &\Rightarrow& \vartheta_k^n(\xi) \in C_m^n(\alpha, \beta) \text{ for } m < k < n \\ \eta \in C_m^n(\alpha, \beta) \cap \alpha &\Rightarrow& \vartheta_m^n(\xi) \in C_m^n(\alpha, \beta) \\ \vartheta_m^n(\alpha) &=& \min(\{\xi < \Omega_{m+1}|C_m^n(\alpha, \xi) \cap \Omega_{m+1} \subseteq \xi \wedge \alpha \in C_m^n(\alpha, \xi)\} \cup \{\Omega_{m+1}\}) \\ \end{eqnarray*} \(n\) is needed to define the function, but the actual value of \(n\) does not affect the function's behavior. So, for example, \(\vartheta_0^1(\alpha) = \vartheta_0^2(\alpha) = \vartheta_0^3(\alpha) = \cdots\) So we can safely eliminate \(n\) and express the function using only two arguments \(\vartheta_m(\alpha)\). Wilken and Weiermann's \(\bar\vartheta\) Wilken and Weiermann's \(\bar\vartheta\) is closely related to Wilken's \(\vartheta\), and their paper closely analyzes the relationship between the two. As before, let \(\Omega_0\) be either \(1\) or a number of the form \(\varepsilon_\alpha\), let \(\Omega_1 > \Omega_0\) be an uncountable regular cardinal and for \(0 < i < \omega\) let \(\Omega_{i+1}\) be the successor cardinal to \(\Omega_i\), and finally let \(\Omega_\omega = \sup_{i < \omega} \Omega_i\). For all \(\beta \leq \Omega_{i+1}\) define the following: \begin{eqnarray*} \Omega_i \cup \beta &\subseteq& \bar{C}_i(\alpha, \beta) \\ \xi, \eta \in \bar{C}_i (\alpha, \beta) &\Rightarrow& \xi + \eta \in \bar{C}_i(\alpha, \beta) \\ j \leq i < \omega \wedge \xi \in \bar{C}_j(\xi, \Omega_{j + 1}) \cap \bar{C}_i(\alpha, \beta) \cap \alpha &\Rightarrow& \bar{\vartheta}_j(\xi) \in \bar{C}_i(\alpha, \beta) \\ \bar{\vartheta}_i(\alpha) &=& \min(\{\xi < \Omega_{i + 1} | \alpha \in \bar{C}_i(\alpha, \xi) \wedge \bar{C}_i(\alpha, \xi) \cap \Omega_{i + 1} \subseteq \xi\} \cup \{\Omega_{i + 1}\}) \\ \end{eqnarray*} Weiermann's \(\vartheta\) The \(\vartheta\) function has the advantage of having only a single argument, at the cost of some added complexity. \begin{eqnarray*} C_0(\alpha, \beta) &=& \beta \cup \{0, \Omega\}\\ C_{n+1}(\alpha, \beta) &=& \{\gamma + \delta, \omega^{\gamma}, \vartheta(\eta) | \gamma, \delta, \eta \in C_n (\alpha, \beta); \eta < \alpha\} \\ C(\alpha, \beta) &=& \bigcup_{n < \omega} C_n (\alpha, \beta) \\ \vartheta(\alpha) &=& \min \{\beta < \Omega | C(\alpha, \beta) \cap \Omega \subseteq \beta \wedge \alpha \in C(\alpha, \beta)\} \\ \end{eqnarray*} \(\vartheta\) follows the archetype of many ordinal collapsing functions — it is defined inductively with a "marriage" to the \(C\) function. Interpreting the equations: * \(C(\alpha, \beta)\) is the set of all ordinals constructible using only the following: ** Zero, all ordinals less than \(\beta\), and \(\Omega\). ** Finite applications of addition, \(\kappa \mapsto \omega^\kappa\), \(\kappa \mapsto \vartheta(\kappa)\) (the latter only if \(\vartheta(\kappa)\) has yet been defined). * \(\vartheta(\alpha)\) is the smallest ordinal \(\beta\) so that \(\alpha \in C(\alpha, \beta)\), and \(\beta\) is greater than all the countable ordinals in \(C(\alpha, \beta)\). Taranovsky's Dmytro Taranovsky, much more recently, developed an OCF that he believes is stronger than ZFC, although the actual strength is an open problem. Let \(\leq\) be a well-ordering of a set \(S\). Let \(0^S\) be the minimal element of \(S\), let \(\text{Succ}_S(a)\) denote the successor of \(a\) in \(S\), let \(\text{Lim}^S\) denote the limit elements of \(S\), and let \(\text{Ld}(a, b)\) be the statement that \(a\) is a limit of a set of elements with degree \(b\). Let \(D\) be the following binary relation over \(S\): *\(\forall a \in S: (a, 0^S) \in D\) *\(\forall a \in S: a \neq 0^S \Rightarrow (0^S, a) \notin D\) *\(\forall b \in \text{Lim}^S: (a, b) \in D \Rightleftarrow \forall c < b: (a, c) \in D\). *\(\forall b: \forall b' = \text{Succ}_S(a): (a, b) \in D \Rightleftarrow \text{Ld}(a, b')\) *\(\forall b: \forall b' = \text{Succ}_S(a): \exists d \in \text{Lim}^S: d \leq b \Rightarrow \forall c: (c, b') \in D \Leftrightarrow (c \leq d \vee \text{Ld}(c, b))\) Sources Category:Functions Category:Transfinite ordinals